1. Field of the Invention
This invention relates to a method and apparatus for image processing, and more particularly to a method and apparatus for image processing which improves the performance of gray scale image transformation.
2. Discussion of the Background
A variety of techniques for representing a continuous tone image in a binary format, also known as halftoning, have been developed. Known halftoning techniques include a dithering method and an error diffusion method, each of which represents each pixel of a continuous tone image with one dot. The dithering method uses a threshold matrix and processing occurs by comparing one threshold value to an adjacent threshold value in the matrix so as to create a repetition characteristic which depends on threshold existence in matrix. The repetition characteristic causes the Moire phenomenon to occur when using the dithering process.
Error diffusion is more preferable as compared to the dithering method because the error-diffusion method is not influenced by the repetition characteristic of the threshold matrix because the error diffusion method do not use a threshold matrix in the binarization process. Error diffusion has the advantages of better resolution and non-repeatable data appearance compared to the dithering method.
However, the error diffusion method has problems in that the dots representing an image are not distributed uniformly to produce a clear image. Instead, the dots appear to be arranged in lines rather than uniformly distributed and therefore, the dots are viewed as noise and the dots are clearly visible as a result of the error diffusion process.
FIG. 1 illustrates a block diagram of a general error diffusion circuit for explaining a principle of the error diffusion method. This error diffusion circuit of FIG. 1 is characterized by the method of error determination. More specifically, an error e(m, n) of an input pixel f(m, n) is determined using a subtracter 113 which is configured to subtract a pixel g(m, n) from a pixel cf(m, n), wherein the pixel cf(m, n) is input to the threshold processing circuit 112 and the pixel g(m, n) is output from the threshold processing circuit 112.
In the error diffusion circuit of FIG. 1, an adder 111 receives an original input pixel f(m, n) from an input source and an error factor from a product/addition circuit 114. An error weighting mask 115 having a coefficient xe2x80x9caxe2x80x9d assigns a weight to an error value e(mxe2x88x92k, nxe2x88x92l) which has been generated during the processing of a pixel (mxe2x88x92k, nxe2x88x92l), wherein the pixel (mxe2x88x92k, nxe2x88x92l) proceeds to the pixel f(m, n) for the number of pixels (k, l). The weighted error value e(mxe2x88x92k, nxe2x88x92l) is sent to the product/addition circuit 114 and then to the adder 111 as an error factor. The adder 111 adds the weighted error value e(mxe2x88x92k, nxe2x88x92l) to the pixel f(m, n) to obtain a corrected value cf(m, n) which is then sent to a threshold processing circuit 112 for outputting a pixel g(m, n). Then, a subtracter 113 generates an error (m, n) using an equation e(m, n)=cf(m, n)xe2x88x92g(m, n).
The above-described error diffusion method has advantages in the aspects of non-periodicity of image and a feature of adaptive modulation.. However, such an error diffusion method also has disadvantages in that a relationship between two adjacent dots are not considered and compensated for, which causes generation of periodic texture such that dots are actually visible to the human eye and causes non-uniform distribution of dots.
The method and apparatus shown in FIG. 1 does not include any means for correcting the problem of unpredictable, non-uniform distribution of dots also referred to as xe2x80x9cperiodic texturexe2x80x9d.
Japanese Laid-Open Patent Publication No. JPAP62-239667 describes a method for image processing which eliminates the above-mentioned disadvantages of the error diffusion. In principle, this method varies the threshold value in a periodic manner so as to arrange dots such that the dots appear to have been made through a mesh screen. However, this method causes generation of moire fringes and deterioration of image quality by causing a reduction of resolution, similar to dithering.
Another method which is related to the present invention described and claimed hereinbelow and which related method has not been publicly disclosed prior to the filing date of the priority application of the present application,. is referred to as an adaptive cell method. The adaptive cell method is disclosed in Laid-Open Japanese Patent Application 11-27528 published on Jan. 29, 1999.
In the adaptive cell method, the relationship between adjacent dots is considered and compensated. More specifically, in this method, a dot is put into the center of a cell or matrix consisting of a number of pixels. This method determines a cell size in accordance with the sum total of input pixel values and arranges each dot at the center of each cell. This method realizes a gray-scale-like transformation which does not generate factitiously-connected dots that deteriorate image quality, while maintaining a gray image having a relatively high resolution, as with the error diffusion, as a result of its advantageous features such as the non-periodicity of the image and the adaptive modulation.
One superior feature of the adaptive cell method is a better circularity of dots. That is, dots are arranged in an approximately even manner in a highlight portion of a gray image. This feature appears particularly around a highlight portion of a gray image, wherein a highlight portion is defined as an image which has been transformed so that a relatively small number of pixels among all of the pixel""s resulting from the binary transformation turn to black or to an ON state.
However, the adaptive cell method has the following drawbacks. One drawback is that a dot of a cell may be inconsistently connected to (D1 and D2 in FIG. 2A) or spaced apart from (E in FIG. 2A) a dot of an adjacent cell in a middle portion (an area where the numbers of black (A in FIG. 2A) and white (B in FIG. 2A) pixels are nearly equal) of an image. As shown in FIG. 2A which illustrates an exemplary bad result of the processing on an image using a three-pixel cell (indicated by a letter C) according to the adaptive cell method, this phenomenon appears particularly when the cell size becomes relatively small (i.e., 3). The reason for the occurrence of this phenomenon is that the adaptive cell method determines the connection of adjacent dots and a location of dot in a cell regardless of dot locations in the surrounding cells.
Another drawback is shown in FIG. 2B where an exemplary bad result of the processing on an image using a 20-pixel cell (indicated by a letter C) according to the adaptive cell method. In this case, 9 black pixels (indicated by a letter F) in the center of the cell form a dot. When a minimum cell size is limited, a plurality of adjacent pixels are determined as a dot. Accordingly, lower-resolution output devices (i.e., a laser printer) may produce an image with relatively large-sized dots. Such an image typically produces an inferior circularity of dots. As seen in FIG. 2b, the dot is so big that the image resolution is decreased even though FIG. 2b is improved relative to FIG. 2a since the large white area in the central portion present in FIG. 2a is avoided in FIG. 2b. 
Also, when a minimum cell size is limited, a problem of lower resolution arises since a cell has a relatively large dot therein and density variations cannot be smaller than the cell.
The present application provides a method for image processing which can overcome the problems and disadvantages described above while greatly improving the quality and performance of gray scale image transformation.
More specifically, the present application provides a novel method and apparatus for performing error diffusion using a unique adaptive cell error diffusion method which transforms n-step gray tone digital image data into m-step gray tone digital image data, wherein n and m are positive whole numbers and n is greater than m.
In one preferred embodiment, a method includes the steps of inputting into an input image data buffer, n-step gray tone digital image data which includes a plurality of input pixels. Each input pixel has an original value which is one of n values representing n density levels. A first transforming step transforms each of the input pixels stored in the input image data buffer into a transformed pixel which has an output pixel value which is equal to one of m values representing m density levels. The first transforming step includes a defining step and a determining step. The defining step defines a pixel set which includes a plurality of non-processed pixels which are located adjacent each other in a processed-pixel recording buffer in accordance with a sum total of the original values of input pixels stored in the input image data buffer at locations corresponding to the plurality of non-processed pixels to be defined as a pixel set. The determining step determines output pixel values from the m values in accordance with a sum total of the original values of input pixels stored in the in put image data buffer at locations corresponding to a plurality of non-processed pixels of the pixel set defined by the defining step. Each of the output pixel values determined by the determining step is assigned to each non-processed pixel included in the pixel set defined by the defining step in a predetermined manner. A second transforming step transforms each of the input pixels stored in the input image data buffer to a transformed pixel which has an output pixel value selected from the m values representing m density levels according to an error diffusion method. Then, a selecting step selects one of a plurality of resultant values of the first and second transforming steps in accordance with an original value of a currently processed input pixel included in the input pixels stored in the input image data buffer.
The selecting step may select the resultant value of the second transforming step when the sum total of the original values of pixels stored in the input image data buffer at the locations corresponding to the plurality of non-processed pixels included in the pixel set defined in the defining step is within a first predetermined range.
Also, the selecting step may select the resultant value of the first transforming step when the original value of the currently processed input pixel included in the input pixels stored in the input image data buffer is within a second predetermined range.
Preferably, the first transforming step includes a correction step for correcting the original value of the currently processed input pixel with error values relating to adjacent pixels located around the currently processed input pixel, and the second transforming step includes a calculation step for calculating a difference between the resultant value of the first transforming step and the original value corrected by the correction step when the selecting step selects the resultant value of the first transforming step and records the difference as an error.
Further, the second transforming step may shift the currently processed input pixel to different pixel according to whether the currently processed input pixel has been assigned an output pixel value, and may perform a product and addition operation relative to the different pixel.
Still further, the second transforming step may change an error weighting mask currently being used to a different mask depending on whether the currently processed input pixel has been assigned an output pixel value, and may perform a product and. addition operation using the different mask.
Preferred embodiments of the present application also provide a storage media which stores a computer program therein for performing image processing to transform n-step gray tone digital image data to m-step gray tone digital image data, wherein n and m are positive whole numbers and n is greater than m. In one preferred embodiment of the apparatus, a storage media includes a computer program which causes a processor to perform the steps of inputting, first transforming, second transforming, and selecting. The inputting step inputs into an input image data buffer, n-step gray tone digital image data which includes a plurality of input pixels. Each input pixel has an original value which is one of n values representing n density levels. The first transforming step transforms each of the input pixels stored in the input image data buffer into a transformed pixel -which has an. output pixel value which is equal to one of m values representing m density levels. The first transforming step includes a defining step for defining a pixel set including a plurality of non-processed pixels located adjacent to each other in a processed-pixel recording buffer in accordance with a sum total of the original values of input pixels stored in the input image data buffer at locations corresponding to the plurality of non-processed pixels to be defined as a pixel set. The first transforming step further includes a determining step for determining output pixel values from the m values,in accordance with a sum total of the original values of input pixels stored in the input image data buffer at locations corresponding to a plurality of non-processed pixels of the pixel set defined by the defining step. Each of the output pixel values determined by the determining step is, assigned to each non-processed pixel included in the pixel set defined by the defining step in a predetermined manner. The second transforming step transforms each of the input pixels stored in the input image data buffer into a transformed pixel which has an output pixel value which is one of the m values representing m density levels according to an error diffusion method. The selecting step selects one of the resultant values of the first and second transforming steps in accordance with an original value of a currently processed input pixel included in the input pixels stored in the input image data buffer.
Preferred embodiments of the present application further provide an image processing apparatus for image processing which transforms n-step gray tone digital image data to m-step gray tone digital image data, wherein n and m are positive whole numbers and n is greater than m. In a preferred embodiment of this apparatus, an image processing apparatus includes an input mechanism, a first transforming mechanism, a second transforming mechanism, and a selecting mechanism. The input mechanism inputs into an input image data buffer, n-step gray tone digital image data including a plurality of input pixels. Each input pixel has an original value which is equal to one of n values representing n density levels. The first transforming mechanism transforms each of the input pixels stored in the input image data buffer into a transformed pixel which has an output pixel value which is equal to one of m values representing m density levels.
The first transforming mechanism includes a defining mechanism which defines a. pixel set including a plurality of non-processed pixels which are located adjacent to each other in a processed-pixel recording buffer in accordance with a sum total of the original values of input pixels stored in the input image data buffer at locations corresponding to the plurality of non-processed pixels to be defined as a pixel set. The first transforming mechanism further includes a determining mechanism which determines output pixel values from the m values in accordance with a sum total of the original values of input pixels stored in the input image data buffer at locations corresponding to a plurality of non-processed pixels of the pixel set defined by the defining mechanism. Each of the output pixel values determined by the determining mechanism is assigned to each non-processed pixel included in the pixel set defined by the defining mechanism in a predetermined manner. The second transforming mechanism transforms each of the input pixels stored in the input image data buffer into a transformed pixel which has an output pixel value out of m values representing m density levels according to an error diffusion method. The selecting mechanism selects one of resultant values of the first and second transforming mechanism in accordance with an original value of a presently processed input pixel-included in the input pixels stored in the input image data buffer.